1. Technical Field
The present invention relates to a method for simulating a multi-queue scheduler using a single queue.
2. Description of the Related Art
In a task scheduling method conventionally used by an operating system (OS) to schedule a plurality of tasks, the tasks are executed sequentially in accordance with a priority level determined for each of the tasks. Furthermore, when plural tasks have the same priority level, the tasks are commonly executed in order on a round-robin basis within a limited time period shown by a timeslice value.
Here, a task scheduling device as referred to herein corresponds to a part of the OS, and tasks are processing units targeted for scheduling, each task generally corresponding to an entire application program (AP) or a section of an AP. As a result of a scheduling operation performed by a task scheduling device, all or a section of an AP corresponding to a task to be executed is sequentially allotted a period of CPU processing time, and executed sequentially by the CPU under the control of a conventional program execution control device, which corresponds to a part of the OS. Hereafter, the “execution of a task” is defined to mean the execution of all or a section of an AP corresponding to the task.
FIG. 1A illustrates an exemplary embodiment of a scheduler and the corresponding run-queue. Illustrated is a CPU, CPU 110, such as a processor the functionality of which is to execute various applications or tasks. In a multi-tasking system, multiple tasks could “appear” to be executing on the CPU 100 simultaneously. The operating system scheduler 120 schedules each task in the system to run on the CPU 110 one after the other in a pre-determined order. Each task is allowed to run for short time durations, called its timeslice. As the task keeps executing, the scheduler tracks its CPU 110 usage, and when the task has executed its allocated/complete timeslice, the scheduler 120 stops the task from further execution and causes any of the other tasks to be scheduled on the CPU 110.
To keep track of various tasks to be executed in a system, the scheduler 120 typically uses some data-structure called run-queue (rq). FIG. 1A illustrates a simple run-queue, a linked list labeled as rq. The run-queue rq has three tasks in it, labeled as A0, A1 and A2. The tasks are arranged in the run-queue in some order, which may be a pre-determined order. For example, it could be sorted by the time of arrival/creation, or by their priority.
A typical algorithm for the scheduler 120 can be described in these steps:                (i) Select a task at the front of the queue.        (ii) Arrange for the CPU to execute the selected task        (iii) As the selected task continues to execute, continuously track its CPU usage.        (iv) When the selected task has run to its allocated timeslice (task timeslice), T, stop the task from further execution        (v) Renew the timeslice for the task to T and move the task to the end of queue.        (vi) Go to step (i)        
Here timeslice, i.e., the task timeslice, is a field in every task that denotes the amount of time left for the task to expire its allocated timeslice. A task is said to have expired its timeslice if its timeslice (task timeslice) field becomes 0. Assuming that the above algorithm is being executed for a task, the following execution pattern can be observed on the CPU in the following order: A0 [T], A1 [T], A2 [T], A0 [T], A1 [T] etc. A0 first executes on the CPU for T seconds (its timeslice), then A1 executes for T seconds, followed by A2 executing for T seconds. Then A0 gets to run again for T seconds. This pattern is repeated until the all tasks are executed completely and the runqueue (hereinafter also referred to as a queue) becomes empty. This simple scheme ensures that all tasks get a fair time on the CPU, without one particular task starving the others for too long.
Grouping tasks in the run-queue into different groups/categories is preferred. All tasks belonging to a root user could be termed the “root” group, while all tasks belonging to the “guest” user could be termed as the “guest” group. The scheduler could use this grouping information to further control the CPU resource allocation, i.e, the scheduler can hand-out/control CPU time among such groups fairly first and then to the tasks in a group. For example, consider that “guest” group has 100 tasks while “root” group has just one task. Going by the simple algorithm described previously in [0006], the “guest” group of tasks can potentially consume all the CPU (since they have more number of tasks) starving the “root” group of tasks (which has just one task). Therefore, a task-group aware scheduler can avoid such starvation by allocating CPU time fairly among groups first and them among the tasks of that group. Thus over some arbitrary interval of K seconds (termed as epoch period), the task-group aware scheduler can ensure that “guest” group of tasks get execution time worth K/2 seconds while “root” group of tasks get execution worth K/2 seconds. The CPU bandwidth allocated to each group is further divided fairly among the tasks of that group.
FIG. 1B illustrates an exemplary embodiment of a scheduler with two run-queues for each task group. To provide fairness to such task-groups, the scheduler could use separate queues for each group. FIG. 1B shows such an example. There are two run-queues, rq0 and rq1. rq0 stores tasks belong to group A, while rq1 stores tasks belonging to group B. In this scenario, the scheduler 120 could follow this scheme to run tasks as follows:                (i) Select a queue from which to pick a task (either rq0 or rq1). The selected queue (representing a task-group) should be such that it has some timeslice (a group timeslice) left in current epoch.        (ii) Select the task at the front of the selected queue.        (iii) Arrange for the CPU 110 to execute the selected task        (iv) As the selected task continues to execute, continuously track its CPU usage and also the CPU usage of the group to which the task(s) belongs.        (v) When the selected task has run to its allocated/complete task timeslice, T, OR when the group, to which the selected task belongs, has run to its allocated/complete group timeslice, K/2, stop the task from further execution.        (vi) Move the task that was just stopped to the end of its queue,                    if the task has expired its task timeslice in Step (v);            else let it remain at the front of the queue.                        (vii) Go to step (i)Here the group timeslice is a field in every group that denotes the time left for the group to expire its allocated timeslice in the current epoch. A group is said to have expired its timeslice if its group timeslice field becomes 0.        
Consider that the epoch interval K, over which group fairness is provided, is 3 T seconds. Thus in 3 T seconds, group A should have received 1.5 T seconds worth of execution while group B should have received 1.5 T seconds worth of execution. the execution pattern observed could be as follows:
                                                                                                                                                            A                        ⁢                                                                                                  ⁢                                                  0                          ⁡                                                      [                            T                            ]                                                                                                                                                                                                  A                        ⁢                                                                                                  ⁢                                                  1                          ⁡                                                      [                                                          T                              /                              2                                                        ]                                                                                                                                                                                                  B                        ⁢                                                                                                  ⁢                                                  0                          ⁡                                                      [                            T                            ]                                                                                                                                                                                                  B                        ⁢                                                                                                  ⁢                                                  1                          ⁡                                                      [                                                          T                              /                              2                                                        ]                                                                                                                                              }                            ->                                                1                  st                                ⁢                                                                  ⁢                                  epoch                  ⁢                                                                          [                                      0                    -                                          3                      ⁢                      T                                                        ]                                                      ⁢                                                  ⁢                                                                                A                    ⁢                                                                                  ⁢                                          1                      ⁡                                              [                                                  T                          /                          2                                                ]                                                                                                                                                              A                    ⁢                                                                                  ⁢                                          2                      ⁡                                              [                        T                        ]                                                                                                                                                              B                    ⁢                                                                                  ⁢                                          1                      ⁡                                              [                                                  T                          /                          2                                                ]                                                                                                                                                              B                    ⁢                                                                                  ⁢                                          2                      ⁡                                              [                        T                        ]                                                                                                                          }                ->                              2            nd                    ⁢                                          ⁢                      epoch            ⁢                                                  [                                          3                ⁢                T                            -              36                        ]                              ⁢                          ⁢                                                  A              ⁢                                                          ⁢                              0                ⁡                                  [                  T                  ]                                                                                                        A              ⁢                                                          ⁢                              1                ⁡                                  [                                      T                    /                    2                                    ]                                                                                                        B              ⁢                                                          ⁢                              0                ⁡                                  [                  T                  ]                                                                                                        B              ⁢                                                          ⁢                              1                ⁡                                  [                                      T                    /                    2                                    ]                                                                          }    ->            3      rd        ⁢                  ⁢          epoch      ⁢                          [                        6          ⁢          T                -                  9          ⁢          T                    ]      Extracting the execution pattern of group A tasks alone, the following data is observed A0 [T], A1 [T] and A2 [T], i.e., A0 executes for T seconds first, then A1 for T seconds followed by A2 for T seconds and it repeats like this afterwards.
FIG. 1C illustrates an exemplary embodiment of a single run-queue hosting multiple groups. It may be advantageous to sometimes avoid the complexity and cost of maintaining such multiple queues. Each additional queue could require additional memory/hardware, the cost of which could be prohibitive in some scenarios. We thus consider a task-group aware scheduler that works on a single run-queue. FIG. 1C shows a runqueue which stores tasks from both group A and B.
A disadvantage with the prior art is ensuring that different tasks of same group are run in the same order as if they had their own run-queue. Accordingly, without a way to provide an improved method for implementing scheduling of tasks on a processor, the promise of this technology may never be fully achieved